package cn.edu.jxau.test;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {

        int[] arr = { 31, 55, 76, 24, 67, 89, 23, 90, 67, 54, 97, 39, 26, 99, 43, 65, 35 };
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序
     * 
     * @param arr 带排序数组
     */
    private static void sort(int[] arr) {

        List<Integer> increaseSequence = new ArrayList<>(); // 递增序列
        int h = 1;
        increaseSequence.add(h);
        while (h < arr.length) {
            h = h * 3 + 1;
            increaseSequence.add(h);
        }
        int[] temp = new int[increaseSequence.size()];
        for (int i = 0; i < temp.length; i++) { // 转成int数组
            temp[i] = increaseSequence.get(i);
        }
        System.out.println("递增序列：" + Arrays.toString(temp));
        sort(arr, temp);

    }

    /**
     * @param arr 带排序数组
     * @param increaseSequence 增长序列
     */
    private static void sort(int[] arr, int[] increaseSequence) {

        for (int i = increaseSequence.length - 1; i >= 0; i--) {
            int span = increaseSequence[i];
            for (int j = span; j < arr.length; j += span) {
                int k = j;
                int temp = arr[k];
                while (k - span >= 0 && temp < arr[k - span]) {
                    arr[k] = arr[k - span];
                    k -= span;
                }
                arr[k] = temp;
            }
        }
    }
}
